package tabu;

import help.Helper;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Calendar;
import java.util.Collections;
import java.util.HashSet;

import dados.Instancia;
import dados.Solucao;
import dados.Torre;

public class BuscaTabu {

	private static final Long TEMPO_MAXIMO = 55000L;

	public Solucao encontraMelhorSolucao(Instancia instancia) {

		final Integer VALOR_TABU = instancia.getQntTorres()/2;
		
		Calendar cal = Calendar.getInstance();
		Long tempoInicial = cal.getTimeInMillis();

		Solucao inicial = encontraSolucaoInicial(instancia);

		instancia.setMelhorSolucao(inicial);
		instancia.setSolucaoAtual(inicial);

		ArrayList<Solucao> vizinhosLista = new ArrayList<Solucao>();
		
		while (Calendar.getInstance().getTimeInMillis() - tempoInicial < TEMPO_MAXIMO) {

			// achar vizinhos
			instancia.calculaVizinhos(instancia.getSolucaoAtual(), vizinhosLista);
			
			Solucao melhorVizinho = null;
			// se nao possui vizinhos, retorna o melhor vizinho tabu valido
			if (vizinhosLista.get(0).getTorreInvertida().getTabu() != 0) {
				melhorVizinho = instancia.getMelhorSolucao();
				Helper.resetaTabu(instancia.getTorresLista().values());
			} else {
				// percorre os vizinhos e retorna o melhor vizinho
				melhorVizinho = vizinhosLista.get(0);
			}

			// atualiza tabela tabu
			for (Torre t : instancia.getTorresLista().values()) {
				if (t.equals(melhorVizinho.getTorreInvertida())) {
					t.setTabu(VALOR_TABU);
				} else {
					t.decrementaTabu();
				}
			}

			// atualiza solucao atual
			instancia.setSolucaoAtual(melhorVizinho);

			// se a solucao atual for melhor que solucao global, atualiza a
			// global
			if ((melhorVizinho.getCusto().compareTo(BigDecimal.ZERO) != 0)
					&& melhorVizinho.getQtdPontos() >= instancia.getQntDados()
					&& (instancia.getMelhorSolucao().getCusto().compareTo(
							melhorVizinho.getCusto()) > 0)) {
				instancia.setMelhorSolucao(melhorVizinho);
			}
			vizinhosLista.clear();
		}

		return instancia.getMelhorSolucao();
	}

	private Solucao encontraSolucaoInicial(Instancia instancia) {

		Solucao inicial = new Solucao();
		

		ArrayList<Torre> listaOrdenacao = new ArrayList<Torre>(instancia.getTorresLista().values());
		// ordena torres pelo custo unitario
		Collections.sort(listaOrdenacao, Helper.COMPARATOR_TORRE);

		// cria hashset para manipular conjuntos de pontos
		HashSet<Integer> pontosCobertosAtual = new HashSet<Integer>();

		// seguindo a ordem estabelecida, adiciona torres ateh preencher o
		// numero de pontos exigidos
		for (Torre torre : listaOrdenacao) {
			// solucao gulosa: adiciona a torre com menor custo unitario
			pontosCobertosAtual.addAll(torre.getPontosCobertos());
			// se houve melhoria, adiciona a solucao
			if (pontosCobertosAtual.size() > inicial.getQtdPontos()) {
				inicial.addTorre(instancia, torre.getIdInteger());
			}
			// se alcancou numero de pontos necessarios, encontrou solucao
			if (inicial.getQtdPontos() >= instancia.getQntDados()) {
				break;
			}
		}
		listaOrdenacao.clear();
		return inicial;
	}

	
}
